home *** CD-ROM | disk | FTP | other *** search
/ Internet Info 1994 March / Internet Info CD-ROM (Walnut Creek) (March 1994).iso / answers / rec / puzzles / archive / analysis < prev    next >
Text File  |  1993-08-17  |  32KB  |  817 lines
  1. Newsgroups: rec.puzzles,news.answers,rec.answers
  2. Path: senator-bedfellow.mit.edu!bloom-beacon.mit.edu!spool.mu.edu!howland.reston.ans.net!europa.eng.gtefsd.com!uunet!questrel!chris
  3. From: chris@questrel.com (Chris Cole)
  4. Subject: rec.puzzles Archive (analysis), part 02 of 35
  5. Message-ID: <puzzles/archive/analysis_745653851@questrel.com>
  6. Followup-To: rec.puzzles
  7. Summary: This is part of an archive of questions
  8.  and answers that may be of interest to
  9.  puzzle enthusiasts.
  10.  Part 1 contains the index to the archive.
  11.  Read the rec.puzzles FAQ for more information.
  12. Sender: chris@questrel.com (Chris Cole)
  13. Reply-To: archive-comment@questrel.com
  14. Organization: Questrel, Inc.
  15. References: <puzzles/archive/Instructions_745653851@questrel.com>
  16. Date: Wed, 18 Aug 1993 06:04:22 GMT
  17. Approved: news-answers-request@MIT.Edu
  18. Expires: Thu, 1 Sep 1994 06:04:11 GMT
  19. Lines: 795
  20. Xref: senator-bedfellow.mit.edu rec.puzzles:24995 news.answers:11515 rec.answers:1915
  21.  
  22. Archive-name: puzzles/archive/analysis
  23. Last-modified: 17 Aug 1993
  24. Version: 4
  25.  
  26.  
  27. ==> analysis/bicycle.p <==
  28. A boy, a girl and a dog go for a 10 mile walk.  The boy and girl can
  29. walk at 2 mph and the dog can trot at 4 mph.  They also have a bicycle
  30. which only one of them (including the dog!) can use at a time.  When
  31. riding, the boy and girl can travel at 12 mph while the dog can pedal
  32. at 16 mph.  What is the shortest time in which all three can complete
  33. the trip?
  34.  
  35. ==> analysis/bicycle.s <==
  36. First note that there's no apparent way to benefit from letting either the
  37. boy or girl ride the bike longer than the other.  Any solution which gets the
  38. boy there faster, must involve him using the bike (forward) more; similarly
  39. for the girl.  Thus the bike must go backwards more for it to remain within
  40. the 10-mile route.  Thus the dog won't make it there in time.  So the solution
  41. assumes they ride the bike for the same amount of time.
  42.  
  43. Also note that there's no apparent way to benefit from letting any of the three
  44. arrive at the finish ahead of the others.  If they do, they can probably take
  45. time out to help the others.  So the solution assumes they all finish at the
  46. same time.
  47.  
  48. The boy starts off on the bike, and travels 5.4 miles.  At this
  49. point, he drops the bike and completes the rest of the trip on foot.  The
  50. dog eventually reaches the bike, and takes it *backward* .8 miles (so the
  51. girl gets to it sooner) and then returns to trotting.  Finally, the girl makes
  52. it to the bike and rides it to the end.  The answer is 2.75 hours.
  53.  
  54. The puzzle is in Vasek Chvatal, Linear Programming, W. H. Freeman & Co.
  55. The generalized problem (n people, 1 bike, different walking and riding speeds)
  56. is known as "The Bicycle Problem".  A couple references are
  57.  
  58. Masuda, S. (1970). "The bicycle problem," University of California, Berkeley:
  59.   Operations Research Center Technical Report ORC 70-35.
  60.  
  61. Chvatal, V. (1983). "On the bicycle problem," Discrete Applied Mathematics 5:
  62.   pp. 165 - 173.
  63.  
  64. As for the linear program which gives the lower bound of 2.75 hours, let
  65. t[person, mode, direction] by the amount of time "person" (boy, girl or dog)
  66. is travelling by "mode" (walk or bike) in "direction" (forward or backwards).
  67. Define Time[person] to be the total time spent by person doing each of these
  68. four activities. The objective is to minimize the maximum of T[person], for
  69. person = boy, girl, dog, e.g.
  70.  
  71.     minimize T
  72.     subject to  T >= T[boy], T >= T[girl], T >= T[dog].
  73.  
  74. Now just think of all the other linear constraints on the variables t[x,y,z],
  75. such as everyone has to travel 10 miles, etc. In all, there are 8 contraints
  76. in 18 variables (including slack variables). Solving this program yields the
  77. lower bound.
  78.  
  79. ==> analysis/boy.girl.dog.p <==
  80. A boy, a girl and a dog are standing together on a long, straight road.
  81. Simulataneously, they all start walking in the same direction:
  82. The boy at 4 mph, the girl at 3 mph, and the dog trots back and forth
  83. between them at 10 mph.  Assume all reversals of direction instantaneous.
  84. In one hour, where is the dog and in which direction is he facing?
  85.  
  86. ==> analysis/boy.girl.dog.s <==
  87. The dog's position and direction are indeterminate, other than that the
  88. dog must be between the boy and girl (endpoints included).  To see this,
  89. simply time reverse the problem.  No matter where the dog starts out,
  90. the three of them wind up together in one hour.
  91.  
  92. This argument is not quite adequate.  It is possible to construct problems
  93. where the orientation changes an infinite number of times initially, but for
  94. which there can be a definite result.  This would be the case if the positions
  95. at time t are uniformly continuous in the positions at time s, s small. 
  96.  
  97. But suppose that at time a the dog is with the girl.  Then the boy is at
  98. 4a, and the time it takes the dog to reach the boy is a/6, because
  99. the relative speed is 6 mph.  So the time b at which the dog reaches the
  100. boy is proportional to a.  A similar argument shows that the time the 
  101. dog next reaches the girl is b + b/13, and is hence proportional to b.
  102. This makes the position of the dog at time (t > a) a periodic function of
  103. the logarithm of a, and thus does not approach a limit as a -> 0.
  104.  
  105. ==> analysis/bugs.p <==
  106. Four bugs are placed at the corners of a square.  Each bug walks always
  107. directly toward the next bug in the clockwise direction.  How far do
  108. the bugs walk before they meet?
  109.  
  110. ==> analysis/bugs.s <==
  111. Since the bugs start out walking perpendicularly, and there is nothing
  112. in the problem to alter this symmetry, the bugs are always walking
  113. perpendicularly.  Since each bug is walking perpendicularly to the line
  114. separating it from the bug chasing it, the gap is closing at the speed
  115. of the chasing bug.  Therefore, each bug walks a distance equal to the
  116. side of the square before it meets the next bug.
  117.  
  118. In order to conveniently express the equation of the bugs' motion,
  119. use standard polar coordinates, and let the first bug's position at
  120. any instant be (r(t), theta(t)).  Assume the initial square is
  121. centered at the origin.
  122.  
  123. Then by symmetry the bugs are always at four corners of some square
  124. centered at the origin, and if they meet they meet at the origin.
  125. Also, each bug is always walking in a direction pi/4 (45 degrees) away
  126. from the radial line to the origin.  This means that in the limit as
  127. the time step goes to zero, the bug travels sec(pi/4) = sqrt(2) units
  128. along its path for every unit of progress made good toward the center.
  129. Since the corners are initially d/sqrt(2) distance from the center,
  130. each bug travels distance d before they meet, assuming they meet at
  131. all.
  132.  
  133. Since a bug's path always crosses radial lines at angle psi = pi/4,
  134. the path is a logarithmic spiral with angle psi = pi/4 and equation
  135.  
  136.   r(t) = e^(a*theta(t) + b)
  137.  
  138. Moreover since the bugs walk clockwise, both r(t) and theta(t)
  139. decrease as t increases, in other words r increases as theta
  140. increases, hence a is positive.  Also, psi = pi/4 gives us
  141.  
  142.   d(r)/d(theta) = r
  143.  
  144. (this is easiest to see by drawing the path for a small time step
  145. delta-t and taking the limit as delta-t goes to 0).  The solution is
  146.  
  147.   r(t) = e^(theta(t) + b)
  148.  
  149. (that is, a = 1).  As we know, this spiral makes infinitely many
  150. "wraps" around the origin as the radius approaches zero, but it does
  151. have finite length from any point inward and its limit point is the
  152. origin, where the bugs will meet (unless one wants to quibble about
  153. the behavior at the exact limit point).
  154.  
  155. How much closer is the bug to the origin after its first complete cycle
  156. around the origin?  Recall that r(0) = d/sqrt(2).  As the bug walks
  157. clockwise around the origin, after one full circuit its angle decreases
  158. from theta(0) to theta(t1), where t1 (the time at which full circuit
  159. occurs) is defined by
  160.  
  161.   theta(t1) = theta(0) - 2*pi
  162.  
  163. Hence
  164.  
  165.   r(0) = e^(theta(0) + b)
  166.   r(t1) = e^(theta(0) - 2*pi + b)
  167.  
  168.   r(t1)/r(0) = e^(-2*pi)
  169.  
  170. The quantity we want is
  171.  
  172.   r(0) - r(t1) = r(0)*(1 - e^(-2*pi))
  173.                = d * (1 - e^(-2*pi))/sqrt(2)
  174.  
  175. ==> analysis/c.infinity.p <==
  176. What function is zero at zero, strictly positive elsewhere, infinitely
  177. differentiable at zero and has all zero derivatives at zero?
  178.  
  179. ==> analysis/c.infinity.s <==
  180. exp(-1/x^2)
  181.  
  182. There are infinitely many other such functions.
  183.  
  184. This tells us why Taylor Series are a more limited device than they might be.
  185. We form a Taylor series by looking at the derivatives of a function at a given
  186. point; but this example shows us that the derivatives at a point may tell us
  187. almost nothing about its behavior away from that point.
  188.  
  189. ==> analysis/cache.p <==
  190. Cache and Ferry (How far can a truck go in a desert?)
  191. A pick-up truck is in the desert beside N 50-gallon gas drums, all full.
  192. The truck's gas tank holds 10 gallons and is empty.  The truck can carry
  193. one drum, whether full or empty, in its bed.  It gets 10 miles to the gallon.
  194. How far away from the starting point can you drive the truck?
  195.  
  196. ==> analysis/cache.s <==
  197. If the truck can siphon gas out of its tank and leave it in the cache,
  198. the answer is:
  199.         { 1/1 + 1/3 + ... + 1/(2 * N - 1) } x 500 miles.
  200.  
  201. A much harder problem occurs when the truck can siphon gas, but if it does,
  202. it must siphon the gas into one of the initial barrels.
  203.  
  204. Now, remarkably, for initial gas values of 50, 100, 150, 200, 250, 300,
  205. and 350 gallons, the two problems give identical optimal distances, viz.
  206.    gal   dist
  207.    ---   ----
  208.     50   500
  209.    100   733.3333
  210.    150   860
  211.    200   948.5714
  212.    250  1016.8254
  213.    300  1072.3810
  214.    350  1117.8355
  215.  
  216. However, for the 8 barrel case (400 gallons), the unlimited cache optimal
  217. distance is 1157.6957, but limited cache is only 1157.2294.
  218.  
  219. What happened is that the unlimited cache optimal solution has started to
  220. siphon out more than 50 gallons (60-80/13 to be exact) of gas on trips
  221. to the first depot.  With a limited cache, the truck can only leave a
  222. maximum of 50 gallons (one barrel worth), and does not have a big
  223. enough gas tank (only ten gallons) to carry around the excess.
  224.  
  225. The limited cache problem is the same as the "Desert Fox" problem
  226. described, but not solved, by Dewdney, July '87 "Scientific American".
  227.  
  228. Dewdney's Oct. '87 Sci. Am. article gives for N=2, the optimal distance
  229. of 733.33 miles.
  230.  
  231. In the Nov. issue, Dewdney lists the optimal distance of 860 miles for
  232. N=3, and gives a better, but not optimal, general distance formula.
  233.  
  234. Westbrook, in Vol 74, #467, pp 49-50, March '90 "Mathematical Gazette",
  235. gives an even better formula, for which he incorrectly claims optimality:
  236.  
  237.   For N = 2,3,4,5,6:
  238.      Dist = (600/1 + 600/3 + ... + 600/(2N-3))  +  (600-100N)/(2N-1)
  239.   For N > 6:
  240.      Dist = (600/1 + 600/3 + ... + 600/9)  +  (500/11 + ... + 500/(2N-3))
  241.  
  242. The following shows that Westbrook's formula is not optimal for N=8:
  243.  
  244.    Ferry  7 drums forward   33.3333 miles   (356.6667 gallons remain)
  245.    Ferry  6 drums forward   51.5151 miles   (300.0000 gallons remain)
  246.    Ferry  5 drums forward   66.6667 miles   (240.0000 gallons remain)
  247.    Ferry  4 drums forward   85.7143 miles   (180.0000 gallons remain)
  248.    Ferry  3 drums forward  120.0000 miles   (120.0000 gallons remain)
  249.    Ferry  2 drums forward  200.0000 miles   ( 60.0000 gallons remain)
  250.    Ferry  1 drums forward  600.0000 miles
  251.                           ---------------
  252.          Total distance = 1157.2294 miles
  253.    (Westbrook's formula = 1156.2970 miles)
  254.  
  255.        ["Ferrying n drums forward x miles" involves (2*n-1) trips,
  256.          each of distance x.]
  257.  
  258. Other attainable values I've found:
  259.    N      Distance
  260.   ---    ---------  (Ferry distances for each N are omitted for brevity.)
  261.     5    1016.8254
  262.     7    1117.8355
  263.    11    1249.2749
  264.    13    1296.8939
  265.    17    1372.8577
  266.    19    1404.1136  (The N <= 19 distances could be optimal.)
  267.    31    1541.1550  (I doubt that this N = 31 distance is optimal.)
  268.   139    1955.5702  (Attainable and probably optimal.)
  269.  
  270. So...where's MY formula?
  271. I haven't found one, and believe me, I've looked.
  272.  
  273. I would be most grateful if someone would end my misery by mailing me
  274. a formula, a literature reference, or even an efficient algorithm that
  275. computes the optimal distance.
  276.  
  277. If you do come up with the solution, you might want to first check it
  278. against the attainable distances listed above, before sending it out.
  279. (Not because you might be wrong, but just as a mere formality to check
  280.  your work.)
  281.  
  282. [Warning:  the Mathematician General has determined that
  283.            this problem is as addicting as Twinkies.]
  284.  
  285. Myron P. Souris
  286. EDS/Unigraphics
  287. souris@ug.eds.com
  288.  
  289. @@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@@
  290.  
  291. The following output comes from some hack programs that I've used to
  292. empirically verify some proofs I've been working on.
  293.  
  294. Initial barrels:   12 (600 gallons)
  295. Attainable distance= 1274.175211
  296.                   Barrels  Distance      Gas
  297.                    Moved    covered     left
  298. >From depot   1:      10     63.1579   480.0000
  299. >From depot   2:       8     50.0000   405.0000
  300. >From depot   3:       7     37.5000   356.2500
  301. >From depot   4:       6     51.1364   300.0000
  302. >From depot   5:       5     66.6667   240.0000
  303. >From depot   6:       4     85.7143   180.0000
  304. >From depot   7:       3    120.0000   120.0000
  305. >From depot   8:       2    200.0000    60.0000
  306. >From depot   9:       1    600.0000     0.0000
  307.  
  308.  
  309. Initial barrels:   40 (2000 gallons)
  310. Attainable distance= 1611.591484
  311.                   Barrels  Distance      Gas
  312.                    Moved    covered     left
  313. >From depot   1:      40      2.5316  1980.0000
  314. >From depot   2:      33     50.0000  1655.0000
  315. >From depot   3:      28     50.0000  1380.0000
  316. >From depot   4:      23     53.3333  1140.0000
  317. >From depot   5:      19     50.0000   955.0000
  318. >From depot   6:      16     56.4516   780.0000
  319. >From depot   7:      13     50.0000   655.0000
  320. >From depot   8:      11     54.7619   540.0000
  321. >From depot   9:       9     50.0000   455.0000
  322. >From depot  10:       8     32.1429   406.7857
  323. >From depot  11:       7     38.9881   356.1012
  324. >From depot  12:       6     51.0011   300.0000
  325. >From depot  13:       5     66.6667   240.0000
  326. >From depot  14:       4     85.7143   180.0000
  327. >From depot  15:       3    120.0000   120.0000
  328. >From depot  16:       2    200.0000    60.0000
  329. >From depot  17:       1    600.0000     0.0000
  330.  
  331. ==> analysis/calculate.pi.p <==
  332. How can I calculate many digits of pi?
  333.  
  334. ==> analysis/calculate.pi.s <==
  335. long a=10000,
  336.     b,
  337.     c=2800,
  338.     d,e,
  339.     f[2801],
  340.     g;
  341.  
  342. main()
  343.    {
  344.     for (;b-c;) f[b++]=a/5;
  345.  
  346.     for (;
  347.     d=0,g=c*2;
  348.     c-=14, printf("%.4d",e+d/a), e=d%a)
  349.     
  350.     for (b=c;
  351.      d+=f[b]*a,f[b]=d%--g,d/=g--,--b;
  352.      d*=b);
  353.    }
  354.  
  355. ==> analysis/cats.and.rats.p <==
  356. If 6 cats can kill 6 rats in 6 minutes, how many cats does it take to
  357. kill one rat in one minute?
  358.  
  359. ==> analysis/cats.and.rats.s <==
  360. The following piece by Lewis Carroll first appeared in ``The Monthly
  361. Packet'' of February 1880 and is reprinted in _The_Magic_of_Lewis_Carroll_,
  362. edited by John Fisher, Bramhall House, 1973.
  363.  
  364. /Larry Denenberg
  365. larry@bbn.com
  366. larry@harvard.edu
  367.  
  368.  
  369.  
  370.  
  371.  
  372.                                  Cats and Rats
  373.  
  374.    If 6 cats kill 6 rats in 6 minutes, how many will be needed to kill 100
  375.    rats in 50 minutes?
  376.  
  377.    This is a good example of a phenomenon that often occurs in working
  378.    problems in double proportion; the answer looks all right at first, but,
  379.    when we come to test it, we find that, owing to peculiar circumstances in
  380.    the case, the solution is either impossible or else indefinite, and needing
  381.    further data.  The 'peculiar circumstance' here is that fractional cats or
  382.    rats are excluded from consideration, and in consequence of this the
  383.    solution is, as we shall see, indefinite.
  384.  
  385.    The solution, by the ordinary rules of Double Proportion, is as follows:
  386.        6 rats   :  100 rats  \
  387.                   >   :: 6 cats : ans.
  388.       50 min.   :    6 min.  /
  389.          .
  390.     . .  ans. = (100)(6)(6)/(50)(6) = 12
  391.  
  392.    But when we come to trace the history of this sanguinary scene through all
  393.    its horrid details, we find that at the end of 48 minutes 96 rats are dead,
  394.    and that there remain 4 live rats and 2 minutes to kill them in: the
  395.    question is, can this be done?
  396.  
  397.    Now there are at least *four* different ways in which the original feat,
  398.    of 6 cats killing 6 rats in 6 minutes, may be achieved.  For the sake of
  399.    clearness let us tabulate them:
  400.       A.  All 6 cats are needed to kill a rat; and this they do in one minute,
  401.           the other rats standing meekly by, waiting for their turn.
  402.       B.  3 cats are needed to kill a rat, and they do it in 2 minutes.
  403.       C.  2 cats are needed, and do it in 3 minutes.
  404.       D.  Each cat kills a rat all by itself, and take 6 minutes to do it.
  405.  
  406.    In cases A and B it is clear that the 12 cats (who are assumed to come
  407.    quite fresh from their 48 minutes of slaughter) can finish the affair in
  408.    the required time; but, in case C, it can only be done by supposing that 2
  409.    cats could kill two-thirds of a rat in 2 minutes; and in case D, by
  410.    supposing that a cat could kill one-third of a rat in two minutes.  Neither
  411.    supposition is warranted by the data; nor could the fractional rats (even
  412.    if endowed with equal vitality) be fairly assigned to the different cats.
  413.    For my part, if I were a cat in case D, and did not find my claws in good
  414.    working order, I should certainly prefer to have my one-third-rat cut off
  415.    from the tail end.
  416.  
  417.    In cases C and D, then, it is clear that we must provide extra cat-power.
  418.    In case C *less* than 2 extra cats would be of no use.  If 2 were supplied,
  419.    and if they began killing their 4 rats at the beginning of the time, they
  420.    would finish them in 12 minutes, and have 36 minutes to spare, during which
  421.    they might weep, like Alexander, because there were not 12 more rats to
  422.    kill.  In case D, one extra cat would suffice; it would kill its 4 rats in
  423.    24 minutes, and have 24 minutes to spare, during which it could have killed
  424.    another 4.  But in neither case could any use be made of the last 2
  425.    minutes, except to half-kill rats---a barbarity we need not take into
  426.    consideration.
  427.  
  428.    To sum up our results.  If the 6 cats kill the 6 rats by method A or B,
  429.    the answer is 12; if by method C, 14; if by method D, 13.
  430.  
  431.    This, then, is an instance of a solution made `indefinite' by the
  432.    circumstances of the case.  If an instance of the `impossible' be desired,
  433.    take the following: `If a cat can kill a rat in a minute, how many would be
  434.    needed to kill it in the thousandth part of a second?'  The *mathematical*
  435.    answer, of course, is `60,000,' and no doubt less than this would *not*
  436.    suffice; but would 60,000 suffice?  I doubt it very much.  I fancy that at
  437.    least 50,000 of the cats would never even see the rat, or have any idea of
  438.    what was going on.
  439.  
  440.    Or take this: `If a cat can kill a rat in a minute, how long would it be
  441.    killing 60,000 rats?'  Ah, how long, indeed!  My private opinion is that
  442.    the rats would kill the cat.
  443.  
  444.  
  445.  
  446. ==> analysis/dog.p <==
  447. A body of soldiers form a 50m-by-50m square ABCD on the parade ground.
  448. In a unit of time, they march forward 50m in formation to take up the
  449. position DCEF. The army's mascot, a small dog, is standing next to its
  450.                                        handler at location A. When the
  451.           B----C----E                  soldiers start marching, the dog
  452.           |    |    |   forward-->     begins to run around the moving
  453.           A----D----F                  body in a clockwise direction,
  454.                                        keeping as close to it as possible.
  455. When one unit of time has elapsed, the dog has made one complete
  456. circuit and has got back to its handler, who is now at location D. (We
  457. can assume the dog runs at a constant speed and does not delay when
  458. turning the corners.)
  459.  
  460. How far does the dog travel?
  461.  
  462. ==> analysis/dog.s <==
  463. Let L be the side of the square, 50m, and let D be the distance the
  464. dog travels.
  465.  
  466. Let v1 be the soldiers' marching speed and v2 be the speed of the dog.
  467. Then v1 = L / (1 time unit) and v2 = v1*D/L.
  468.  
  469. Let t1, t2, t3, t4 be the time the dog takes to traverse each side of
  470. the square, in order.  Find t1 through t4 in terms of L and D and solve
  471. t1+t2+t3+t4 = 1 time unit.
  472.  
  473. While the dog runs along the back edge of the square in time t1, the
  474. soldiers advance a distance d=t1*v1, so the dog has to cover a distance
  475. sqrt(L^2 + (t1*v1)^2), which takes a time t1=sqrt(L^2 + (t1*v1)^2)/v2.
  476. Solving for t1 gives t1=L/sqrt(v2^2 - v1^2).
  477.  
  478. The rest of the times are t2 = L/(v2-v1), t3 = t1, and t4 = L/(v2+v1).
  479.  
  480. In t1+t2+t3+t4, eliminate v2 by using v2=v1*D/L and eliminate v1 by
  481. using v1=L/(1 time unit), obtaining
  482.  
  483.         2 L (D + sqrt(D^2-L^2)) / (D^2 - L^2) = 1
  484.  
  485. which can be turned into
  486.  
  487.         D^4 - 4LD^3 - 2L^2D^2 + 4L^3D + 5L^4 = 0
  488.  
  489. which has a root D = 4.18113L = 209.056m.
  490.  
  491. ==> analysis/e.and.pi.p <==
  492. Without finding their numerical values, which is greater, e^(pi) or (pi)^e?
  493.  
  494. ==> analysis/e.and.pi.s <==
  495. e^(pi).  Put x = pi/e - 1 in the inequality e^x > 1+x  (x>0).
  496.  
  497. ==> analysis/functional/distributed.p <==
  498.      Find all f: R -> R, f not identically zero, such that
  499. (*)     f( (x+y)/(x-y) ) = ( f(x)+f(y) )/( f(x)-f(y) ).
  500.  
  501. ==> analysis/functional/distributed.s <==
  502. 1)  Assuming f finite everywhere, (*) ==> x<>y ==> f(x)<>f(y)
  503.  
  504. 2)  Exchanging x and y in (*) we see that f(-x) = -f(x).
  505.  
  506. 3)  a <> 0 ==> f((a-a)/(a+a)) = (f(a)-f(a))/(f(a)+f(a)) ==> f(0) = 0.
  507.  
  508. 4)  a <> 0 ==> f((a+0)/(a-0)) = f(a)/f(a) ==> f(1) = 1.
  509.  
  510. 5)  x<>y, y<>0 ==> f(x/y) =
  511. f( ((x+y)/(x-y) + (x-y)/(x-y)) / ((x+y)/(x-y) - (x-y)/(x-y)) = f(x)/f(y)
  512. ==> f(xy) = f(x)f(y) by replacing x with xy and by noting that
  513. f(x*1) = f(x)*1 and f(x*0) = f(x)*f(0).
  514.  
  515. 6)  f(x*x) = f(x)*f(x) ==> f(x) > 0 if x>0.
  516.  
  517. 7)  Let a=1+\/2, b=1-\/2; a,b satisfy (x+1)/(x-1) = x ==>
  518. f(x) = (f(x)+1)/(f(x)-1) ==> f(a)=a, f(b)=b.  f(1/\/2) = f((a+b)/(a-b))
  519. = (a+b)/(a-b) = 1/\/2 ==> f(2) = 2.
  520.  
  521. 8)  By induction and the relation f((n+1)/(n-1)) = (f(n)+1)/(f(n)-1)
  522. we get that f(n)=n for all integer n.  #5 now implies that f fixes
  523. the rationals.
  524.  
  525. 9)  If x>y>0 (*) ==> f(x) - f(y) = f(x+y)/f((x+y)/(x-y)) > 0 by #6.
  526. Thus f is order-preserving.
  527.  
  528. Since f fixes the rationals *and* f is order-preserving, f must be the
  529. identity function.
  530.  
  531. This was E2176 in _The American Mathematical Monthly_ (the proposer was
  532. R. S. Luthar).
  533.  
  534. ==> analysis/functional/linear.p <==
  535. Suppose f is non-decreasing with
  536.   f(x+y) = f(x) + f(y) + C   for all real x, y.
  537. Prove: there is a constant A such that f(x) = Ax - C  for all x.
  538. (Note: continuity of f is not assumed in advance.)
  539.  
  540. ==> analysis/functional/linear.s <==
  541. By induction f(mx) = m(f(x)+C)-C.  Let x=1/n, m=n and find that
  542. f(1/n) = (1/n)(f(1)+C)-C.  Now let x=1/n and find that f(m/n) =
  543. (m/n)(f(1)+C)-C.  f(-x+x) = f(-x) + f(x) + C ==> f(-x) = -2C - f(x)
  544. (since f(0) = -C) ==> f(-m/n) = -(m/n)(f(1)+C)-C.  Since f is
  545. monotonic ==> f(x) = x*(f(1)+C)-C for all real x (Squeeze Theorem).
  546.  
  547. ==> analysis/integral.p <==
  548. If f is integrable on (0,inf) and differentiable at 0, and a > 0, and:
  549.  
  550.       inf           f(x)
  551.    Int        ----------------  dx is defined
  552.        0             x
  553.  
  554. show:
  555.  
  556.       inf     ( f(x) - f(ax) )  
  557.    Int        ----------------  dx   = f(0) ln(a)
  558.        0             x
  559.  
  560. ==> analysis/integral.s <==
  561. First, note that if f(0) is 0, then by substituting u=ax in
  562. the integral of f(x)/x, our integral is the difference of two
  563. equal integrals and so is 0 (the integrals are finite because f is
  564. 0 at 0 and differentiable there.  Note I make no requirement of
  565. continuity).
  566.  
  567. Second, note that if f is the characteristic function of the
  568. interval [0, 1]--- i.e.
  569.  
  570.         1, 0<=x<=1
  571.     f (x) =
  572.         0 otherwise
  573.  
  574. then a little arithmetic reduces our integral to that of
  575. 1/x from 1/a to 1 (assuming a>1; if a <= 1 the reasoning is similar),
  576. which is ln(a) = f(0)ln(a) as required.  Call this function g.
  577.  
  578. Finally, note that the operator which takes the function f to the
  579. value of our integral is linear, and that every function meeting the
  580. hypotheses (incidentally, I should have said `differentiable from the right',
  581. or else replaced the characteristic function of [0,1] above by that of
  582. (-infinity, 1]; but it really doesn't matter) is a linear combination of
  583. one which is 0 at 0 and g, to wit
  584.  
  585.     f(x) = f(0)g(x) + (f(x) - g(x)f(0)).
  586.  
  587. ==> analysis/irrational.stamp.p <==
  588. You have an ink stamp which is so amazingly precise that, when inked
  589. and pressed down on the plane, it makes every circle of irrational
  590. radius (centered at the center of the stamp) black.
  591.  
  592. Question:  Can one use the stamp three times and make every point
  593. in the plane black?  [assume plane was white to begin with, and
  594. ignore the fact that no such stamp is physically possible]
  595.  
  596. ==> analysis/irrational.stamp.s <==
  597. Yes.  Center the stamp at (0,0), (1,0), and (0,pi).
  598.  
  599. Suppose there is a point (x,y) which is not covered.
  600. Then there are rational numbers a,b,c satisfying the following equations:
  601.  
  602.   (1)   x^2   +   y^2     =  a
  603.   (2) (x-1)^2 +   y^2     =  b
  604.   (3)   x^2   + (y-pi)^2  =  c
  605.  
  606. Subtract (2) from (1) and solve for x.  Thus x is rational.
  607. From equation (2), y is algebraic.  But equation (3) implies
  608. that y is transcendental, contradiction.
  609.  
  610. ==> analysis/minimum.time.p <==
  611. N people can walk or drive in a two-seater to go from city A to city B.  What
  612. is the minimum time required to do so?
  613.  
  614. ==> analysis/minimum.time.s <==
  615. Let the speed of the car be v, the speed of a walking person be u, and
  616. the distance between cities by L.  We want to minimize T, the time t
  617. at which all persons are at displacement x=L (city B), when they all
  618. start at displacement x=0 (city A) at time t=0.
  619.  
  620. I'll assume that the solution has everyone starting out from city A at
  621. the same time t=0 arriving in city B at the same time t=T so nobody is
  622. standing around idly waiting.  Let's plot everyone's movements on a
  623. graph showing coordinates (t,x).  Then at time t just after 0, (N-2)
  624. walkers are on the line L0 through (0,0) with slope dx/dt = u, and 2
  625. in the car are on a line through (0,0) with slope v, and at t just
  626. before T, (N-2) walkers are on the line L1 through (T,L) with slope u,
  627. and 2 in the car are on a line through (T,L) with slope v.  Obviously
  628. L1 lies "above" L0 (greater x coordinate given the same t coordinate).
  629. In between t=0 and t=T, the car zigzags between L0 and L1 along lines
  630. of slope v and -v, picking up people from L0 and dropping them off at
  631. L1.  I will not prove that this is the optimal strategy; in fact you
  632. can make an infinite number of variations on it which all come up with
  633. the same elapsed time.
  634.  
  635. Now examine the graph again.  Say the car travels distance r between
  636. picking someone up and dropping that person off, and distance s back
  637. to pick up the next person.  The car makes (N-1) trips forward and
  638. (N-2) trips back to pick up and ferry everyone, so its total travel is
  639.  
  640.     vT = (N - 1)r + (N - 2)s = (N - 2)(r + s) + r
  641.  
  642. Moreover the car makes (r-s) net displacement on each round trip, plus
  643. r displacement on the extra forward trip, so
  644.  
  645.     L = (N - 2)(r - s) + r
  646.  
  647. Note that a person walks distance (r-s) in the time it takes the car to
  648. go (r+s), so 
  649.  
  650.     r - s = (u/v)(r + s)
  651.  
  652. A little algebraic manipulation of this equation shows us that
  653.  
  654.     r - s = r * 2u/(v + u)
  655.     r + s = r * 2v/(v + u)
  656.  
  657. Plug this into the equation for L, and we get the first important
  658. piece of information, how far the car should drive before dropping off
  659. the passenger (once you know this, you tell it to the driver and this
  660. guarantees the people get to B in minimum time):
  661.  
  662.     L = r + (N - 2) r * 2u/(v + u)
  663.       = r * (v + u + (N - 2)*2u)/(v + u)
  664.  
  665.            v + u
  666.     r = ------------ L
  667.         2uN + v - 3u
  668.  
  669. We can also find out what the elapsed time T will be:
  670.  
  671.  
  672.     vT = (N - 2)r*2v/(v + u) + r
  673.        = r * ((N - 2)*2v + v + u)/(v + u)
  674.  
  675.         1   2vN - 3v + u
  676.     T = - * ------------ r
  677.         v      v + u
  678.  
  679. Therefore
  680.  
  681.         2vN - (3v - u)
  682.     T = -------------- (L/v)
  683.          2uN + v - 3u
  684.  
  685.  
  686. -- David Karr (karr@cs.cornell.edu)
  687.  
  688.  
  689. ==> analysis/particle.p <==
  690. What is the longest time that a particle can take in travelling between two
  691. points if it never increases its acceleration along the way and reaches the
  692. second point with speed V?
  693.  
  694. ==> analysis/particle.s <==
  695. Assumptions:
  696.  
  697. 1. x(0) = 0; x(T) = X
  698.  
  699. 2. v(0) = 0; v(T) = V
  700.  
  701. 3. d(a)/dt <= 0
  702.  
  703. Solution:
  704.  
  705. a(t) = constant = A = V^2/2X which implies T = 2X/V.
  706.  
  707. Proof:
  708.  
  709. Consider assumptions as they apply to f(t) = A * t - v(t):
  710.  
  711. 1. integral from 0 to T of f = 0
  712.  
  713. 2. f(0) = f(T) = 0
  714.  
  715. 3. d^2(f)/dt^2 <= 0
  716.  
  717. From the mean value theorem, f(t) = 0.  QED.
  718.  
  719. ==> analysis/period.p <==
  720. What is the least possible integral period of the sum of functions
  721. of periods 3 and 6?
  722.  
  723. ==> analysis/period.s <==
  724. Period 2.  Clearly, the sum of periodic functions of periods 2 and
  725. three is 6.  So take the function which is the sum of that function of
  726. period six and the negative of the function of period three and you
  727. have a function of period 2.
  728.  
  729. This proves that a period-2 solution exists, but not that it is minimal.
  730. Since we're talking about integers, the only lower possibility is 1.
  731. But the sum or difference of a period-1 and a period-3 function must have
  732. period 3, not 6, therefore 1 is indeed impossible.
  733.  
  734. ==> analysis/rubberband.p <==
  735. A bug walks down a rubber band which is attached to a wall at one end and a car
  736. moving away from the wall at the other end. The car is moving at 1 m/sec while
  737. the bug is only moving at 1 cm/sec. Assuming the rubber band is uniformly and
  738. infinitely elastic, will the bug ever reach the car?
  739.  
  740. ==> analysis/rubberband.s <==
  741. Let w = speed of bug and N = ratio of car speed/bug speed = 100.  Paint N+1
  742. equally spaced stripes on the rubberband.  When the bug is standing on one
  743. stripe, the next stripe is moving away from him at a speed slightly < w
  744. (relative to him).  Since he is walking at w, clearly the bug can reach
  745. the next stripe.  But once he reaches that stripe, the next one is only
  746. receeding at < w.  So he walks on down to the car, one stripe at a time.
  747.  
  748. The bug starts gaining on the car when he is at the next to last stripe.
  749.  
  750. ==> analysis/sequence.p <==
  751. Show that in the sequence: x, 2x, 3x, .... (n-1)x (x can be any real number)
  752. there is at least one number which is within 1/n of an integer.
  753.  
  754. ==> analysis/sequence.s <==
  755. Throw 0 into the sequence; there are now n numbers, so some pair must
  756. have fractional parts within 1/n of each other; their difference is
  757. then within 1/n of an integer.
  758.  
  759. ==> analysis/snow.p <==
  760. Snow starts falling before noon on a cold December day.  At noon a
  761. snow plow starts plowing a street.  It travels 1 mile in the first hour,
  762. and 1/2 mile in the second hour.  What time did the snow start
  763. falling??
  764.  
  765. You may assume that the plow's rate of travel is inversely proportional
  766. to the height of the snow, and that the snow falls at a uniform rate.
  767.  
  768. ==> analysis/snow.s <==
  769. 11:22:55.077 am.
  770.  
  771. Method:
  772.  
  773. Let b = the depth of the snow at noon, a = the rate of increase in the
  774. depth.  Then the depth at time t (where noon is t=0) is at+b, the
  775. snowfall started at t_0=-b/a, and the snowplow's rate of progress is 
  776. ds/dt = k/(at+b).
  777.  
  778. If the snowplow starts at s=0 then s(t) = (k/a) log(1+at/b).  Note that
  779. s(2 hours) = 1.5 s(1 hour), or  log(1+2A/b) = 1.5 log(1+A/b), where
  780. A = (1 hour)*a.  Letting x = A/b we have (1+2x)^2 = (1+x)^3.  Solve for
  781. x and t_0 = -(1 hour)/x.
  782.  
  783. The exact answer is 11:(90-30 Sqrt[5]).
  784.  
  785. _American Mathematics Monthly_, April 1937, page 245
  786. E 275.  Proposed by J. A. Benner, Lafayette College, Easton. Pa.
  787.  
  788. The solution appears, appropriately, in the December 1937 issue,
  789. pp. 666-667.  Also solved by William Douglas, C. E. Springer,
  790. E. P. Starke, W. J.  Taylor, and the proposer.
  791.  
  792. See R.P. Agnew, "Differential Equations," 2nd edition, p. 39 ff.
  793.  
  794. ==> analysis/tower.p <==
  795. R = N ^ (N ^ (N ^ ...)).  What is the maximum N>0 that will yield a finite R?
  796.  
  797. ==> analysis/tower.s <==
  798. ANSWER: e^(1/e)
  799.  
  800. Let N be the number in question and R the result of the process. Then
  801. R can be defined recursively by the equation:
  802.     (1) R = N^R
  803. Taking the logarithm of both sides of (1):
  804.     (2) ln(R) = R * ln(N)
  805. Dividing (2) by R and rearranging:
  806.     (3) ln(N) = ln(R) / R
  807. Exponentiating (3):
  808.     (4) N = R^(1/R)
  809. We wish to find the maximum value of N with respect to R. Find the
  810. derivative of N with respect to R and set it equal to zero:
  811.     (5) d(N)/d(R) = (1 - ln(R)) / R^2 = 0
  812. For finite values of R, (5) is satisfied by R = e. This is a maximum of
  813. N if the second derivative of N at R = e is less than zero.
  814.     (6) d2(N)/d2(R) | R=e = (2 * ln(R) - 3) / R^3 | R=e = -1 / e^3 < 0
  815. The solution therefore is (4) at R = e:
  816.     (7) Nmax = e^(1/e)
  817.